The time required to execute computer executable instructions (i.e. programs) can be reduced by applying compiler optimizations. Programs that consist of many short procedures benefit in particular from inter-procedural optimizations. The object-oriented approach to programming promotes the use of short procedures (commonly known as methods) to encapsulate functionality and to provide modularity and abstraction. These procedures are frequently virtual procedures.
A common inter-procedural optimization technique is inlining. Inlining reduces the overhead of a procedure call by replacing the procedure call with a called (i.e. target) procedure directly in the body of a calling procedure. Inlining also increases the opportunities for applying other compiler optimization techniques. An exemplary description of inlining is provided in A Comparative Study Of Static And Dynamic Heuristics For Inlining, Matthew Arnold, Stephen Fink, Vivek Sarkar, and Peter F. Sweeney, ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization, January 2000 which is incorporated in its entirety herein by reference.
When a virtual procedure call is executed, a declared procedure or one of several procedures that can override it is actually invoked. The declared procedure and the overriding procedures are known as target procedures of the virtual procedure call. The overriding of a target procedure for a virtual procedure call is a function of the dynamic class definition (i.e. polymorphism) of an object containing the virtual procedure. The dynamic nature of virtual procedures creates important challenges for implementing inter-procedural optimizations. An approach known as call devirtualization can be used to introduce compiler optimization in the case of a virtual procedure call.
Many devirtualization techniques are known for reducing the runtime overhead of virtual procedure calls for various object-orient languages by inlining of the procedure or replacing the virtual procedure call with a direct procedure call. One such technique is guarded devirtualization. In guarded devirtualization a class or method (i.e. procedure) test is used to ensure that the inlined procedure or the direct call to a target method is valid. This technique is highly effective in dynamically-typed object-oriented languages but is much less effective in statically-typed object-oriented languages such as, for example, Java. Exemplary descriptions of guarded devirtualization are provided in Inlining of Virtual Methods, David Detlefs and Ole Agesen, ECOOP '99 and Thin Guards: A simple and Effective Technique for Reducing the Penalty of Dynamic Class Loading (2202), Matthew Arnold, Barbara G. Ryder, Proceedings of the Sixteenth European Conference on Object Oriented Programming (Malaga, Spain, June 2002) which are incorporated in their entirety herein by reference.
Another devirtualization technique known as direct devirtualization eliminates the guard test by applying whole program analysis and optimizations using a static compiler. Direct virtualization is generally based on a closed-world assumption in which no dynamic class loading is allowed. Therefore, this technique is less effective when applied to languages such as Java™ which permit dynamic class loading without placing generally unacceptable constraints on the use of important features of the language.
Yet another technique known as direct devirtualization with code patching employs inlining of a target procedure at the virtual procedure call site. The inlined instructions are executed until an assumption that permits devirtualization is invalidated such as, for example when the target procedure is overridden. When the assumption is invalidated, the compiler performs code patching to cause the virtual procedure call to be executed instead of the inlined procedure.
In dynamic languages dynamically loaded classes may be encountered at runtime. Call devirtualization based on inter-class analysis may be invalidated when new classes are loaded. A mechanism for dealing with new classes that appear at runtime is to detect invalidated optimizations at runtime and to correct them using recompilation. Such a deoptimization mechanism can discover if a newly loaded class invalidates any existing inlinings and correct every such inlining by recompiling the appropriate procedures. A difficulty with this mechanism occurs when a procedure that needs to be recompiled is currently executing. There is a set of circumstances (known as preexistence) that avert this complication. Currently-executing procedures that contain invalidated inlinings are allowed to continue executing the original code until they exit. Only subsequent invocations of the procedure are to execute the recompiled code.
A further refinement of this approach is to correct invalidated inlining by replacing a single instruction with a jump to the original virtual call. This reduces the runtime penalty associated with recompiling and is known as code patching. An exemplary description of code patching is provided in A Direct Devirtualization Technique with the Code Patching Mechanism, Kazuaki Ishizaki, Toshiaki Yasue, Motohiro Kawahito, Hideaki Komatsu, IPSJ Transactions on Programming Vol. 43 No. SIG08-011, which is incorporated in its entirety herein by reference.
Invariant argument preexistence (herein after preexistence) is said to occur when the receiver object for a procedure call has been allocated before the invocation of a caller procedure. When preexistence occurs, the class of the receiver object does not change in the scope of invocation of the caller procedure. Even when a class loading event that overrides the called procedure occurs, the called procedure associated with the receiver object will not be overridden during the execution of the caller procedure. This property can be exploited in implementing compiler optimizations such as direct devirtualization. When preexistence occurs, the caller procedure does not need to be recompiled during the execution of the calling procedure and therefore mechanisms such as backup paths, on-stack replacement and other similar mechanisms are not required. The caller procedure does need to be recompiled or code patched at its next invocation in which the called procedure has been overridden. An exemplary description of preexistence is provided in Inlining of Virtual Methods (supra).
What is needed is a method that permits additional inter-procedural compiler optimizations of computer executable instructions associated with objects subject to run-time polymorphism.